package com.infosys.cabplanner.scheduler;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import com.infosys.cabplanning.common.domain.CoordinatesPathBean;
import com.infosys.cabplanning.common.domain.GeoCoordidnate;

public class ShortestPathAlgorithm {

	private List<GeoCoordidnate> nodes;
	private List<CoordinatesPathBean> edges;
	private Set<GeoCoordidnate> settledNodes;
	private Set<GeoCoordidnate> unSettledNodes;
	private Map<GeoCoordidnate, GeoCoordidnate> predecessors;
	private Map<GeoCoordidnate, Integer> distance;
	
	public List<GeoCoordidnate> getNodes() {
		return nodes;
	}

	public void setNodes(List<GeoCoordidnate> nodes) {
		this.nodes = nodes;
	}

	public List<CoordinatesPathBean> getEdges() {
		return edges;
	}

	public void setEdges(List<CoordinatesPathBean> edges) {
		this.edges = edges;
	}

	public Set<GeoCoordidnate> getSettledNodes() {
		return settledNodes;
	}

	public void setSettledNodes(Set<GeoCoordidnate> settledNodes) {
		this.settledNodes = settledNodes;
	}

	public Set<GeoCoordidnate> getUnSettledNodes() {
		return unSettledNodes;
	}

	public void setUnSettledNodes(Set<GeoCoordidnate> unSettledNodes) {
		this.unSettledNodes = unSettledNodes;
	}

	public Map<GeoCoordidnate, GeoCoordidnate> getPredecessors() {
		return predecessors;
	}

	public void setPredecessors(Map<GeoCoordidnate, GeoCoordidnate> predecessors) {
		this.predecessors = predecessors;
	}

	public Map<GeoCoordidnate, Integer> getDistance() {
		return distance;
	}

	public void setDistance(Map<GeoCoordidnate, Integer> distance) {
		this.distance = distance;
	}

//	public ShortestPathAlgorithm(TripPlannerGraph graph) {
//		
//		this.setNodes(graph.getDestinations());
//		this.setEdges(graph.getConnections());
//	}
	
public ShortestPathAlgorithm(List<GeoCoordidnate> destinations, List<CoordinatesPathBean> connections) {
		
		this.setNodes(destinations);
		this.setEdges(connections);
	}
	
	  public void execute(GeoCoordidnate source) {
		    settledNodes = new HashSet<GeoCoordidnate>();
		    unSettledNodes = new HashSet<GeoCoordidnate>();
		    distance = new HashMap<GeoCoordidnate, Integer>();
		    predecessors = new HashMap<GeoCoordidnate, GeoCoordidnate>();
		    distance.put(source, 0);
		    unSettledNodes.add(source);
		    while (unSettledNodes.size() > 0) {
		    	GeoCoordidnate node = getMinimum(unSettledNodes);
		      settledNodes.add(node);
		      unSettledNodes.remove(node);
		      findShortestDistance(node);
		    }
		  }

	  public LinkedList<GeoCoordidnate> getPath(GeoCoordidnate target) {
		    LinkedList<GeoCoordidnate> path = new LinkedList<GeoCoordidnate>();
		    GeoCoordidnate step = target;
		    // check if a path exists
		    if (predecessors.get(step) == null) {
		      return null;
		    }
		    path.add(step);
		    while (predecessors.get(step) != null) {
		      step = predecessors.get(step);
		      path.add(step);
		    }
		    // Put it into the correct order
//		    Collections.reverse(path);
		    return path;
		  }
	
	private void findShortestDistance(GeoCoordidnate node) {
	    List<GeoCoordidnate> adjacentNodes = getNeighbors(node);
	    for (GeoCoordidnate target : adjacentNodes) {
	      if (getShortestDistance(target) > getShortestDistance(node) + getDistance(node, target)) {
	        distance.put(target, getShortestDistance(node) + getDistance(node, target));
	        predecessors.put(target, node);
	        unSettledNodes.add(target);
	      }
	    }

	  }
	
	private int getShortestDistance(GeoCoordidnate destination) {
	    Integer d = distance.get(destination);
	    if (d == null) {
	      return Integer.MAX_VALUE;
	    } else {
	      return d;
	    }
	  }
	
	private int getDistance(GeoCoordidnate node, GeoCoordidnate target) {
		
	    for (CoordinatesPathBean edge : edges) {
	      if (edge.getSource().equals(node) && edge.getDestination().equals(target)) {
	        return edge.getDistance();
	      }
	    }
	    
	    // this will never get executed
	    return 0;
	  }

	  private List<GeoCoordidnate> getNeighbors(GeoCoordidnate node) {
	    List<GeoCoordidnate> neighbors = new ArrayList<GeoCoordidnate>();
	    for (CoordinatesPathBean edge : edges) {
	      if (edge.getSource().equals(node) && !isSettled(edge.getDestination())) {
	        neighbors.add(edge.getDestination());
	      }
	    }

	    return neighbors;
	  }
	  
	  private GeoCoordidnate getMinimum(Set<GeoCoordidnate> vertexes) {
		  GeoCoordidnate minimum = null;
		    for (GeoCoordidnate vertex : vertexes) {
		      if (minimum == null) {
		        minimum = vertex;
		      } else {
		        if (getShortestDistance(vertex) < getShortestDistance(minimum)) {
		          minimum = vertex;
		        }
		      }
		    }
		    return minimum;
		  }
	  
	  private boolean isSettled(GeoCoordidnate vertex) {
		    return settledNodes.contains(vertex);
		  }
	
	
}
